package com.ly.algorithm.leetcode;

import java.util.*;

/**
 * @Classname Problem40
 * @Description
 *
 * 给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
 *
 * candidates 中的每个数字在每个组合中只能使用一次。
 *
 * 说明：
 *
 * 所有数字（包括目标数）都是正整数。
 * 解集不能包含重复的组合。 
 * 示例 1.txt:
 *
 * 输入: candidates = [10,1.txt,2,7,6,1.txt,5], target = 8,
 * 所求解集为:
 * [
 *   [1.txt, 7],
 *   [1.txt, 2, 5],
 *   [2, 6],
 *   [1.txt, 1.txt, 6]
 * ]
 * 示例 2:
 *
 * 输入: candidates = [2,5,2,1.txt,2], target = 5,
 * 所求解集为:
 * [
 *   [1.txt,2,2],
 *   [5]
 * ]
 *
 *
 * @Date 2020/9/10 14:14
 * @Author 冷心影翼
 */
public class Problem40 {
    public static void main(String[] args) {
        Solution40 solution40 = new Solution40();
        List<List<Integer>> lists = solution40.combinationSum2(new int[]{10,1,2,7,6,1,5}, 8);
        for (List<Integer> list : lists) {
            System.out.println(list);
        }
    }
}

//1.txt 2 2 2 5    5
//  1.txt     2
// 2  2
// 2  2
class Solution40 {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        if(candidates == null || candidates.length == 0) {
            return null;
        }
        Arrays.sort(candidates);
        LinkedList<Integer> path = new LinkedList<>();
        int begin = 0;
        dfs(path,res,candidates,begin,target);
        return res;
    }

    public void dfs(LinkedList<Integer> path,List<List<Integer>> res,int[] candidates ,int begin,int target) {
        if(target == 0) {
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i=begin;i<candidates.length;i++) {
            //剪去右边的分支
            // 5 6 7 8  t = 8  5
            if(target<candidates[i]) {
                break;
            }
            // 1.txt 2 2 2 3    b = 3   相同跳过这一层
            if(i>begin && candidates[i-1] == candidates[i]) {
                continue;
            }
            path.add(candidates[i]);
            dfs(path,res,candidates,i+1,target-candidates[i]);
            path.removeLast();
        }
    }
}